// https://leetcode.cn/problems/longest-palindrome/description/

// 算法思路总结：
// 1. 统计每个字符出现频率
// 2. 累加所有字符的偶数部分构造回文对
// 3. 如有剩余字符可放一个在回文中心
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    int longestPalindrome(string s) 
    {
        int m = s.size();
        unordered_map<char, int> up;

        for (const char& ch : s)
            up[ch]++;

        int ret = 0;
        for (const auto& pair : up)
            ret += pair.second / 2 * 2;

        return ret < s.size() ? ret + 1 : ret;
    }
};

int main()
{
    string s1 = "abccccdd", s2 = "a";
    Solution sol;

    cout << sol.longestPalindrome(s1) << endl;
    cout << sol.longestPalindrome(s2) << endl;

    return 0;
}